1. Field of the Invention
The present invention relates to state recovery in processors including an out-of-order execution section. Specifically, the present invention relates to recovery mechanisms for recovering processor state following a branch misprediction.
2. Description of Related Art
In order to increase processing speed of computer processors, "pipelined" structures have been developed. A pipelined computer processor includes a plurality of stages that operate independently of each other. When a first instruction has completed execution in one of the pipeline stages, the instruction moves on to the next stage, and a second instruction moves into the stage vacated by the first instruction. Any point in time, multiple instructions are being processed simultaneously in the pipeline because each stage may hold an instruction. For example, at one instant in time, a ten-stage pipeline may be processing ten instructions. In order to further increase processing speed, processors termed "superscalar" processors have been designed with multiple pipelines that process instructions simultaneously when adjacent instructions have no data dependencies between them. Even greater parallelism and higher performance can be provided by an out-of-order processor that includes multiple parallel units, in which instructions are processed in parallel in any efficient order that takes advantage of whatever opportunities for parallel processing that may be provided by the instruction code.
Out-of-order processing can greatly increase throughput over conventional processing in which instructions are processed sequentially one after the other. However, out-of-order processing greatly increases complexity over a simple sequential processor. One area of increased complexity relates to state recovery following an unpredicted change of instruction flow. At any particular time during execution, the out-of-order execution section may have many instructions in the execution stage, some awaiting scheduling, some being executed, and some having completed execution but awaiting retirement. In the event that a change of instruction flow is detected during execution of an instruction, the instructions preceding that instruction must proceed to retirement, but the instructions following the instruction flow changing instruction should be discarded. In other words, the state of the processor at the time of the change in instruction flow must be recovered in order for execution to continue properly. State recovery puts the pipeline in the state that it would have been had those instructions not been processed. Due to the heavily pipelined nature (i.e., many stages), and the large number of instructions that may be in the out-of-order section, a state recovery mechanism must be established in such a way to efficiently and correctly recover state following a branch misprediction, an exception, or an interrupt.
Therefore, one particular problem with pipelined processing is the issue of state recovery following an unexpected change of instruction flow, which can be caused by internal or external events such as interrupts, problems with program execution such as exceptions, and explicit instructions such as branches, calls, and returns. Each of those occurrences may give rise to a situation where multiple instructions within the pipeline must be flushed and the state recovered.
For efficient processing of instructions, the number of instructions to be flushed should be kept to a minimum, and the mechanism that accomplishes the flushing should be as efficient as possible. However, implementation of an efficient flushing and state recovery mechanism can be difficult. Often, the actual target instruction cannot be verified with certainty until a number of subsequent instructions are already in various processing stages within the pipeline. For example, a target of a branch instruction cannot be known with certainty until after the instruction has been executed.
A branch instruction is an instruction that expressly changes the flow of program. Branch instructions can be conditional or unconditional: an unconditional branch instruction is always taken, and a conditional branch instruction is either "taken" or "not taken" dependent upon the results of the condition expressed within the instruction. The "takenness" of an unconditional branch is not known with certainty until the time of execution of the branch instruction, when many instructions have already subsequently entered the pipeline. In order to avoid waiting until after the branch instruction has been executed, many processors predict a branch target before the execution stage. If the prediction turns out to be incorrect, then the state following the branch is flushed, and the actual target is fetched. Branch prediction has been proven highly effective at increasing the performance of pipelined computer processors.